"""
NC14 按之字形顺序打印二叉树
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=117&&tqId=37722&&companyId=239&rp=1&ru=/company/home/code/239&qru=/ta/job-code-high/question-ranking
"""

from typing import List


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot TreeNode类
# @return int整型二维数组
#


class Solution:

    def method1(self, node: TreeNode) -> List[List[int]]:
        if not node:
            return []

        res = []
        tmp = [node]  # 记录下一层的节点
        level = 0  # 记录层级
        while tmp:
            _res = []
            size = len(tmp)
            for _ in range(size):
                # 遍历节点的时候，都是从左到右
                n = tmp.pop(0)
                if n.left:
                    tmp.append(n.left)
                if n.right:
                    tmp.append(n.right)

                # # 保存值的时候，偶数层（从0开始），从右边添加。奇数层，从左边插入值
                # if level % 2 == 0:
                #     _res.append(n.val)
                # else:
                #     _res.insert(0, n.val)
                _res.append(n.val)

            # 奇数层，反转下
            if level % 2 != 0:
                _res.reverse()

            res.append(_res)
            level += 1

        return res

    def Print(self, pRoot: TreeNode) -> List[List[int]]:
        # write code here
        return self.method1(pRoot)
